/* 
 * Implement strStr()
 * kmp
 */

#include "../func.h"

void compute_prefix(const char *pattern, int next[])
{
    int i;
    int j = -1;
    const int m = strlen(pattern);

    next[0] = j;
    for (i = 1; i < m; ++i)
    {
        while (j > -1 && pattern[j + 1] != pattern[i])
            j = next[j];
        if (pattern[i] == pattern[j + 1])
            ++j;
        next[i] = j;
    }
}

int kmp(const char *text, const char *pattern)
{
    int i, j = -1;
    const int n = strlen(text);
    const int m = strlen(pattern);
    if (0 == m)
        return 0;

    int *next = (int *)malloc(sizeof(int) * m);
    compute_prefix(pattern, next);

    for (i = 0; i < n; ++j)
    {
        while (j > -1 && pattern[j + 1] != text[i])
            j = next[j];
        if (text[i] == pattern[j + 1])
            ++j;
        if (j == m - 1)
        {
            free(next);
            return i - j;
        }
    }
    free(next);
    return -1;
}